package IC.asm;


import java.util.ArrayList;
import java.util.List;

import util.LinkedList;

import IC.AST.DefaultVisitor;
import IC.AST.PropogatingVisitor;
import IC.AST.nodes.*;

import IC.Analyzer.SymTabEntry;
import IC.Analyzer.Types.*;

import IC.asm.Instruction;
import IC.asm.Instruction.*;

import IC.asm.LoweringContext.ContextKind;

import IC.asm.decl.*;
import IC.asm.operands.*;
import IC.asm.operands.MachineReg.Regs;

import IC.lir.ClassInfo;
import IC.asm.PreProcessor;

/**
 * list of optimizations:
 * 1. let any expression be calculated in several ways:
 * 		a. Register - save the value to a given register
 * 		b. DoubleLabel - treat the expression as boolean and generate code
 * 			which branches to these labels according to the boolean value
 * 		c. AnyOperand - let the expression decide which type of operand to return
 * 
 * 2. Immediates return themselves and so are local variables. they do not
 * 		save them selves to registers. 
 * 
 * 3. The binary expression handler takes advantage of accumulation, and evaluates
 * 		the expressions so one has to be in a register and the other can be
 * 		in any operand. 
 * 
 * 5. The function call does not take any registers to save the parameters
 * 		but rather takes the computed arguments as AnyOperand
 * 
 * 6. The array index accepts both immediates and registers
 * 
 * 
 *
 */
public class LoweringVisitor extends
DefaultVisitor<LoweringContext, List<ASMEntry>> implements
PropogatingVisitor<LoweringContext, List<ASMEntry>> {

	private static class DoubleLabel implements LoweringContext {
		public Label trueLabel;
		public Label falseLabel;

		/**
		 * @param trueLabel
		 * @param falseLabel
		 */
		public DoubleLabel(Label trueLabel, Label falseLabel) {
			this.trueLabel = trueLabel;
			this.falseLabel = falseLabel;
		}

		public ContextKind getKind() {
			return ContextKind.DBLLabel;
		}
	}

	/**
	 * holds a context which propogate any operand
	 * can do "conversion" and return what is requested
	 * @author root
	 *
	 */
	private static class AnyOperand implements LoweringContext {
		private Operand op = null;
		private	Kind	kind;

		private enum Kind {
			Reg, Imm, Mem;
		}

		public void set(RegOperand op) 	{ this.op = op; kind = Kind.Reg; }
		public void set(MemOperand op) 	{ this.op = op; kind = Kind.Mem; }
		public void set(ImmOperand op) 	{ this.op = op; kind = Kind.Imm; }

		/**
		 * convert to register 
		 * @param list
		 * @return
		 */
		public RegOperand getReg(List<ASMEntry> list) {
			assert(op != null);
			switch (kind) {
			case Reg:
				return (RegOperand)op;
			default:
				RegOperand Rtmp = new VirtualReg();
				list.add(new Instruction(Ops.MOV, op, Rtmp));
				return Rtmp;
			}
		}

		public boolean isReg() { return kind.equals(Kind.Reg); }
		public boolean isImm() { return kind.equals(Kind.Imm); }
		public boolean isMem() { return kind.equals(Kind.Mem); }
		
		/**
		 * convert to register or immediate
		 * @param list
		 * @return
		 */
		public Operand getRegImm(List<ASMEntry> list) {
			assert(op != null && list != null);

			switch (kind) {
			case Reg: case Imm:
				return op;
			default:
				RegOperand Rtmp = new VirtualReg();
				list.add(new Instruction(Ops.MOV, op, Rtmp));
				return Rtmp;
			}
		}

		public Operand getOp() {
			assert(op != null);
			return op;
		}

		public ContextKind getKind() {
			return ContextKind.AnyOperand;
		}
	}

	/* loop start and end labels (for break, continus) */
	private Label loopTest, loopEnd;

	/* end of method */
	private Label methodEnd;

	/* the 'this' value' */
	private RegOperand regThis; 

	/* holds the program root */
	private Program root;


	/**
	 * Constructs a new visitor
	 */
	private LoweringVisitor() throws Exception {
	}


	/**
	 * Translates a program to ASM
	 * 
	 * @param root
	 *            the program
	 */
	public static void Process(Program root) throws Exception {
		LoweringVisitor v = new LoweringVisitor();
		PreProcessor.Process(root);
		v.root = root;
		root.accept(v, null);
	}

	public List<ASMEntry> visit(Program that, LoweringContext context)
	throws Exception {
		for (ClassDecl cls : that.getClasses()) {
			if (!cls.getClassID().equals("Library")) {
				cls.accept(this, context);
			}
		}
		return null;
	}

	/**
	 *	if (a) then b; else c;
	 *	-----------------------		
	 *		visit(a,null,false)
	 *		visit(b)
	 *		jmp end
	 *	false:
	 *		visit(c)
	 *	end:
	 * 	
	 *  if a then b;
	 *	-------------
	 *		visit(a,null,false)
	 *		visit(b)
	 *	false:
	 *
	 */
	public List<ASMEntry> visit(IfStmt that, LoweringContext context)
	throws Exception {
//		VirtualReg.resetCounter();

		// translate the condition
		Label labelFalse = new Label();
		List<ASMEntry> list = makeComment("if");
		list.addAll(that.getCondition().accept(this,
				new DoubleLabel(null, labelFalse)) );

		// translate the If statement
		list.addAll(that.getIfStmt().accept(this, null));

		if (that.getElseStmt() != null) {
			// add jump-to-end instruction
			Label labelEnd = new Label();
			list.add(new Instruction(Ops.JMP, labelEnd));
			list.add(new LabelDecl(labelFalse));
			list.addAll(that.getElseStmt().accept(this, null));
			list.add(new LabelDecl(labelEnd));
		} else {
			list.add(new LabelDecl(labelFalse));
		}
		return list;
	}

	/**
	 *	while (a) b;
	 *	------------
	 *		jump test
	 *	start:
	 *		visit(b)
	 *	test:
	 *		visit(a,start,null)
	 *	end:
	 *
	 */
	public List<ASMEntry> visit(WhileStmt that, LoweringContext context)
	throws Exception {
//		VirtualReg.resetCounter();

		// save previous values
		Label prevLoopTest = loopTest;
		Label prevLoopEnd = loopEnd;

		// create 3 labels: start, end, test
		Label labelStart = loopTest = new Label();
		Label labelTest = new Label();
		loopEnd = new Label();
		DoubleLabel dblLabel = new DoubleLabel(labelStart, null);

		// first, jump to `test' label
		List<ASMEntry> list = makeComment("while");
		list.add(new Instruction(Ops.JMP, labelTest));

		// then, add the loop restart label
		list.add(new LabelDecl(labelStart));

		// translate body
		list.addAll(that.getBody().accept(this, null));

		// translate condition
		list.add(new LabelDecl(labelTest));
		list.addAll(that.getCondition().accept(this, dblLabel));
		list.add(new LabelDecl(loopEnd));

		// restore
		loopTest = prevLoopTest; 
		loopEnd = prevLoopEnd;

		return list;
	}

	/** 
	 * visit a method - 
	 * save the method code
	 */
	public List<ASMEntry> visit(MethodDecl that, LoweringContext context)
	throws Exception {

		List<ASMEntry> list;

		// save 'this' to a register in virtual functions
		VirtualReg.resetCounter();
		if (that.isStatic()) {
			regThis = null;
			list = new LinkedList<ASMEntry>();
		}
		else {
			regThis = new VirtualReg();
			list = new LinkedList<ASMEntry>(new Instruction(Ops.MOV, 
					new MemOperand(new MachineReg(Regs.ebp), 8),
					regThis));
		}

		// create end-of-method label
		methodEnd = new Label(that.getLabel()+"_epilogue");
		
		// translate the method body (statement block)
		list.addAll(that.getBody().accept(this, null));
		list.add(new LabelDecl(methodEnd));
		
		// save the code of this method
		that.setAsmCode(list);
		that.setNumLocals(VirtualReg.getAllCount());
		return null;
	}

	/**
	 * visit a statement block - 
	 * concatinate all statements
	 */
	public List<ASMEntry> visit(StmtBlock that, LoweringContext context)
	throws Exception {
		List<ASMEntry> list = new LinkedList<ASMEntry>();
		for (Statement s : that.getStmts()) {
			list.addAll(s.accept(this, null));
		}
		return list;
	}

	/**
	 * break;
	 * ------
	 * 		jump loopEnd
	 */
	public List<ASMEntry> visit(BreakStmt that, LoweringContext context)
	throws Exception {
		LinkedList<ASMEntry> list = makeComment("break");
		list.add(new Instruction(Ops.JMP, loopEnd));
		return list;
	}

	/**
	 * continue;
	 * ---------
	 * 		jump loopTest
	 */
	public List<ASMEntry> visit(ContinueStmt that, LoweringContext context)
	throws Exception {
		LinkedList<ASMEntry> list = makeComment("continue");
		list.add(new Instruction(Ops.JMP, loopTest));
		return list;
	}

	/**
	 * a = b;
	 * -------
	 * 		translateAssignment( a <- b )
	 */
	public List<ASMEntry> visit(AssignStmt that, LoweringContext context)
	throws Exception {
//		VirtualReg.resetCounter();
		LinkedList<ASMEntry> list = makeComment("assignment");
		list.addAll(translateAssignment(that.getDest(), that.getSrc()));
		return list;
	}

	/**
	 * return a;
	 * ---------
	 * 		visit(a,Rinterm)
	 * 		Return a
	 * 
	 * return;
	 * -------
	 * 		Return 9999
	 * 
	 */
	public List<ASMEntry> visit(ReturnStmt that, LoweringContext context)
	throws Exception {
//		VirtualReg.resetCounter();
		List<ASMEntry> list = makeComment("return");
		if (that.getExpr() != null) {
			list.addAll(that.getExpr().accept(this, new MachineReg(Regs.eax)));
		} 
		list.add(new Instruction(Ops.JMP, methodEnd));
		return list;
	}

	/**
	 * Type a;
	 * ------
	 * 
	 * Type a = b;
	 * -----------
	 * 		translateAssignment( a <- b )
	 *
	 */
	public List<ASMEntry> visit(VarDeclStmt that, LoweringContext context)
	throws Exception {
//		VirtualReg.resetCounter();
		String id = that.getVar().getID();
		that.getSymTab().resolve(id).setReg(new VirtualReg());
		LinkedList<ASMEntry> list = makeComment("`"+id+"' declaration");
		if (that.getInit() != null) {
			list.addAll(translateAssignment(that.getVar(), that.getInit()));
		}
		return list;
	}

	/**
	 * a();
	 * ----
	 * 		visit(a,Rdummy)
	 * 
	 */
	public List<ASMEntry> visit(MethodCallStmt that, LoweringContext context)
	throws Exception {
//		VirtualReg.resetCounter();
		LinkedList<ASMEntry> list = makeComment("method call");
		list.addAll(that.getCall().accept(this, new AnyOperand()));
		return list;
	}

	/**
	 * A.m(e1,e2)
	 * ----------
	 * 		visit(e1, Rp1)
	 * 		visit(e2, Rp2)
	 * non-boolean:
	 * 		StaticCall _A_m(e1,e2), Rdest
	 * boolean:
	 * 		StaticCall _A_m(e1,e2), Rtmp
	 * 		addBranchCode(Rtmp, context)
	 * 
	 * 
	 * Library.m(e1,e2)
	 * ----------------
	 * 		visit(e1, Rp1)
	 * 		visit(e2, Rp2)
	 * non-boolean:
	 * 		Library		_A_m(e1,e2), Rdest
	 * boolean:
	 * 		Library		_A_m(e1,e2), Rtmp
	 * 		addBranchCode(Rtmp, context)
	 * 
	 * 
	 */
	public List<ASMEntry> visit(StaticCall that, LoweringContext context)
	throws Exception {
		List<ASMEntry> list = new LinkedList<ASMEntry>();
		Label methodLabel;
		if (that.getClassID().equals("Library")) {
			/** handle Library calls */
			methodLabel =  new Label("__"+that.getMethodID());
		} 
		else {
			/** handle typical static calls * */

			// find method declaration
			ClassInfo classInfo = getClassInfo(that.getClassID());
			String methodID = that.getMethodID();
			SymTabEntry eMethod = classInfo.getClassDecl().
			getStaticSymTab().resolve(methodID);
			assert(eMethod != null);

			MethodDecl methodDecl = (MethodDecl) eMethod.getDeclNode();
			methodLabel = new Label(methodDecl.getLabel());
		}

		/** emit the call */
		translateCall(list, methodLabel, null, context, that.getArgs());
		return list;
	}

	/**
	 * [ o. ] a(e1,e2)
	 * --------------
	 * 		visit(o, Robj) |  Move	this, Robj
	 * 		visit(e1, Rp1)
	 * 		visit(e1, Rp2)
	 * 		VirtualCall Robj.offset-of-method(type-of(o|this),a)(params), Rdest
	 * 	if (boolean-context):
	 * 		Compare		1, Rdest
	 * 		JumpTrue	trueLabel
	 * 		JumpFalse	falseLabel
	 * 
	 */
	public List<ASMEntry> visit(VirtualCall that, LoweringContext context)
	throws Exception {
		List<ASMEntry> list = new LinkedList<ASMEntry>();
		
		// put instance to Robj and get classInfo
		ClassInfo classInfo;
		RegOperand Rinst;

		Expression inst = that.getInstance();
		if (inst != null) {
			// Robj <- translate(o)
			AnyOperand any = new AnyOperand();
			list = inst.accept(this, any);
			Rinst = any.getReg(list);
			classInfo = getClassInfoByExpr(inst);
		} else {
			// Rtmp <- this
			list = new LinkedList<ASMEntry>();
			Rinst = regThis;
			classInfo = 
				getClassInfoByType(that.getSymTab().resolve("this").getType());
		}

		// null pointer check
		nullPtrCheck(list, Rinst);
		
		RegOperand Rdv = new VirtualReg();
		list.add(new Instruction(Ops.MOV, new MemOperand(Rinst), Rdv));

		// find method offset
		String methodID = that.getMethodID();
		int offs = classInfo.getMethodOffset(methodID);

		/** emit the call */
		translateCall(list, new MemOperand(Rdv, offs*4), Rinst, context, that.getArgs());

		return list;
	}

	/**
	 * a[i]
	 * ----
	 * lvalue:
	 * 		visit(a, Rarr)
	 * 		visit(i, Rindex)
	 * 		MoveArray	Rsrc, Rarr[Rindex]
	 * 	
	 * rvalue (boolean):
	 * 		visit(a, Rarr)
	 * 		visit(i, Rindex)
	 * 		MoveArray	Rarr[Rindex], Rtmp
	 * 		Compare		1, Rtmp
	 * 		JumpTrue	labelTrue
	 * 		JumpFalse	labelFalse
	 * 
	 * rvalue (non-boolean):
	 * 		visit(a, Rarr)
	 * 		visit(i, Rindex)
	 * 		MoveArray	Rsrc, Rarr[Rindex]
	 * 		MoveArray	Rarr[Rindex], Rdest
	 * 
	 */
	public List<ASMEntry> visit(ArrayElmVar that, LoweringContext context)
	throws Exception {
		// put array pointer to a register
		AnyOperand any = new AnyOperand();
		List<ASMEntry> list = that.getArray().accept(this, any);
		RegOperand Rarr = any.getReg(list);

		// null pointer check
		nullPtrCheck(list, Rarr);
		
		// put array index to a register
		RegOperand Rindex = new VirtualReg();
		RegOperand Rtmp = new VirtualReg();
		
		list.addAll(that.getIndex().accept(this, Rindex));
		list.add(new Instruction(Ops.MOV, Rindex, Rtmp));
		
		list.add(new CommentEntry("array bounds check"));
		list.add(new Instruction(Ops.CMP, new IntImmediate(0), Rtmp));
		list.add(new Instruction(Ops.JL, new Label("labelABE")));
		list.add(new Instruction(Ops.SAL, new IntImmediate(2), Rtmp));
		list.add(new Instruction(Ops.CMP, Rtmp, new MemOperand(Rarr, -4)));
		list.add(new Instruction(Ops.JLE, new Label("labelABE")));

		if (that.isLvalue()) {
			assert (context.getKind()==ContextKind.AnyOperand);
		}

		list.add(new CommentEntry("access array"));
		save(list, new MemOperand(Rarr, 0, Rtmp), context);
		return list;
	}

	/**
	 * a
	 * --
	 *	member-var: translateMemberVar(this, a)
	 *	local:		translaveVar(a_v{depth})
	 *	param:		translateVar(a)
	 *
	 */
	public List<ASMEntry> visit(SimpleVar that, LoweringContext context)
	throws Exception {
		String id = that.getID();
		SymTabEntry e = that.getSymTab().resolve(id);
		List<ASMEntry> list = new LinkedList<ASMEntry>();

		if (e.isMemberVar()) {
			// have translateMemberVar complete the work
			SymTabEntry eThis = that.getSymTab().resolve("this");
			translateMemberVar(list, regThis,
					getClassInfoByType(eThis.getType()), 
					that.getID(), that.isLvalue(), context);
		} 
		else {
			if (e.isLocalVar()) {
				save(list, e.getReg(), context);
			}
			else {
				save(list, new MemOperand(new MachineReg(Regs.ebp), 
									e.getOffset()), context);
			}
		} 
		return list;
	}

	/**
	 * a.b
	 * ---
	 * 		translateMemberVar(a.b)
	 */
	public List<ASMEntry> visit(MemberVar that, LoweringContext context)
	throws Exception {
		// resolve instance
		Expression inst = that.getInstance();
		RegOperand Rinst = new VirtualReg();
		List<ASMEntry> list = inst.accept(this, Rinst);

		// null pointer check
		nullPtrCheck(list, Rinst);
		
		// have translateMemberVar complete the work
		translateMemberVar(list, Rinst, getClassInfoByExpr(inst), 
				that.getID(), that.isLvalue(), context);
		return list;
	}

	/**
	 * generates code that returns an immediate value to a context
	 * @param val the immediate value
	 * @param context the context
	 * @return the code
	 */
	private List<ASMEntry> generateLiteralCode(ImmOperand val,
			LoweringContext context) {
		LinkedList<ASMEntry> list = new LinkedList<ASMEntry>();
		save(list, val, context);
		return list;	
	}

	/**
	 * N
	 * --
	 * 		Move N, dest
	 */
	public List<ASMEntry> visit(IntLiteral that, LoweringContext context)
	throws Exception {
		return generateLiteralCode(new IntImmediate(that.getValue()),context);
	}

	/**
	 * null
	 * ----
	 * 		Move 0, dest
	 * 
	 */
	public List<ASMEntry> visit(NullLiteral that, LoweringContext context)
	throws Exception {
		return generateLiteralCode(new IntImmediate(0),context);
	}

	/**
	 * "foo"
	 * ------
	 * 		Move literal_of("foo"), dest
	 */
	public List<ASMEntry> visit(StringLiteral that, LoweringContext context)
	throws Exception {
		Label strLiteral = 
				new Label(root.getStringLiterals().get(that.getValue()));
		return generateLiteralCode(strLiteral,context);
	}

	/**
	 * true/false
	 * -----------
	 * 		Jump truelabel / Jump FalseLabel / NOP
	 * 
	 * 		Move 1/0, Rdest
	 * 
	 */
	public List<ASMEntry> visit(BoolLiteral that, LoweringContext context)
	throws Exception {
		switch (context.getKind()) {
		case REG:
		case AnyOperand:
		case Mem:
			ImmOperand val = new IntImmediate(that.getValue()?1:0);
			return generateLiteralCode(val,context);
		case DBLLabel:
			DoubleLabel dblLabel = (DoubleLabel) context;
			Label destLabel = that.getValue() 
					? dblLabel.trueLabel : dblLabel.falseLabel;
			return (destLabel == null) 
					? new LinkedList<ASMEntry>() 
					: new LinkedList<ASMEntry>(new Instruction(Ops.JMP, destLabel));
		default:
			assert(false);
		}
		throw new Exception();
	}

	/**
	 * a.length
	 * ---------
	 * 		visit(a,RArr)
	 * 		ArrayLength	Rarr, Rdest
	 * 
	 */
	public List<ASMEntry> visit(LengthExpr that, LoweringContext context)
	throws Exception {
		RegOperand Rarr = new VirtualReg();
		List<ASMEntry> list = that.getArray().accept(this, Rarr);
		
		// null pointer check
		nullPtrCheck(list, Rarr);
		
		MemOperand len = new MemOperand(Rarr, -4);
		RegOperand Rtmp;
		switch (context.getKind()) {
		case REG:
			Rtmp = (RegOperand)context;
			break;
		case AnyOperand:
			Rtmp = new VirtualReg();
			((AnyOperand)context).set(Rtmp);
			break;
		case Mem:
			Rtmp = new VirtualReg();
			break;
		default:
			throw new Exception();
		}
		list.add(new Instruction(Ops.MOV, len, Rtmp));
		list.add(new Instruction(Ops.SAR, new IntImmediate(2), Rtmp));
		save(list, Rtmp, context);
		return list;
	}

	/**
	 * new Type[expr];
	 * ------------
	 * 		visit(expr,Rsize)
	 * 		Library __allocateArray(Rsize), Rdest
	 */
	public List<ASMEntry> visit(NewArrayExpr that, LoweringContext context)
	throws Exception {
		assert(ContextKind.CanBeLval.contains(context.getKind()));

		// translate the size expression
		AnyOperand any = new AnyOperand();
		List<ASMEntry> list = that.getSize().accept(this, any);
	
		// multiply size by 4
		RegOperand Rsize = any.getReg(list);
		RegOperand Rtmp = new VirtualReg();
		list.add(new Instruction(Ops.MOV, Rsize, Rtmp));
		list.add(new CommentEntry("negative size check"));
		list.add(new Instruction(Ops.CMP, new IntImmediate(0), Rtmp));
		list.add(new Instruction(Ops.JLE, new Label("labelAAE")));
		list.add(new Instruction(Ops.SAL, new IntImmediate(2), Rtmp));
		
		translateCall(list, new Label("__allocateObject"), context, Rtmp);
		list.add(new CommentEntry("fix size on allocate"));
		list.add(new Instruction(Ops.MOV, Rtmp, 
				new MemOperand(new MachineReg(Regs.eax), -4)));
		
		return list;
	}

	/**
	 * new A();
	 * --------
	 * 		Library __allocateObject(size-of-A), Rdest
	 * 		MoveField	_DV_A, Rdest.0
	 * 		
	 */
	public List<ASMEntry> visit(NewClassExpr that, LoweringContext context)
	throws Exception {
		assert(ContextKind.CanBeLval.contains(context.getKind()));

		List<ASMEntry> list = new LinkedList<ASMEntry>();

		// make parameters list of Library call
		ClassInfo classInfo = getClassInfo(that.getClassID());
		int size = classInfo.getSize();

		translateCall(list, new Label("__allocateObject"), 
						context, new IntImmediate(size));

		// save dispatch vector
		list.add(new Instruction(
				Ops.MOV, 
				new Label(classInfo.getDVName()), 
				new MemOperand(new MachineReg(Regs.eax))));
		return list;
	}

	/**
	 * this
	 * -----
	 * 		Move this, Rdest
	 */
	public List<ASMEntry> visit(ThisExpr that, LoweringContext context)
	throws Exception {
		assert (! context.getKind().equals(ContextKind.DBLLabel));
		LinkedList<ASMEntry> list = new LinkedList<ASMEntry>();
		save(list, regThis, context);
		return list;
	}

	/**
	 * -a 
	 * ---------
	 * 		visit(a,Rdest)
	 * 		Neg	Rdest
	 * !a
	 * ---------
	 * 		visit(a,<true-false labels swapped>)
	 * 		
	 */
	public List<ASMEntry> visit(UnaryExpr that, LoweringContext context)
	throws Exception {
		List<ASMEntry> list = null;
		Operator op = that.getOp();
		RegOperand Rdest;
		switch (op) {
		case MINUS:
			switch (context.getKind()) {
			case REG:
				Rdest = (RegOperand)context;
				list = that.getOperand().accept(this, Rdest);
				list.add(new Instruction(Ops.NEG, Rdest));
				break;
			case AnyOperand:
				AnyOperand any = (AnyOperand)context;
				list = that.getOperand().accept(this, any);
				if (any.isImm()) {
					// negate immediate immediately
					IntImmediate imm = (IntImmediate)any.getOp();
					any.set(new IntImmediate( -imm.getVal() ));
				}
				else {
					// negate register or memory
					list.add(new Instruction(Ops.NEG, any.getOp()));
				}
				break;
			case Mem:
				list = that.getOperand().accept(this, (MemOperand)context);
				list.add(new Instruction(Ops.NEG, (MemOperand)context));
			default: 
				assert(false);
			}
			break;
		case LNEG:
			switch (context.getKind()) {
			case REG:
				Rdest = (RegOperand)context;
				list = that.getOperand().accept(this, Rdest);
				list.add(new Instruction(Ops.XOR, new IntImmediate(1), Rdest));
				break;
			case Mem:
				list = that.getOperand().accept(this, (MemOperand)context);
				list.add(new Instruction(Ops.XOR, new IntImmediate(1),
							(MemOperand)context));
				break;
			case AnyOperand:
				AnyOperand any = (AnyOperand)context;
				list = that.getOperand().accept(this, any);
				if (any.isImm()) {
					// negate immediate immediately
					IntImmediate imm = (IntImmediate)any.getOp();
					any.set(new IntImmediate( 1 - imm.getVal() ));
				}
				else {
					// negate register or memory
					list.add(new Instruction(Ops.XOR, new IntImmediate(1), 
								any.getOp()));
				}
				break;
			case DBLLabel:
				// swap labels!!
				DoubleLabel dblLabel = (DoubleLabel)context;
				list = that.getOperand().accept(this, 
						new DoubleLabel(dblLabel.falseLabel,dblLabel.trueLabel));
				break;
			default:
				assert(false);
			}
			break;
		default:
			assert(false);
		}
		return list;
	}

	/**
	 * Arithmetic:
	 * =============================
	 * for op in {+,-,*,/,%}:
	 *
	 * a op b 
	 * ---------
	 * 		visit(a,Rdest)               (every instruction visiting a and b)
	 * 		visit(b,Rtmp)
	 * 		op	Rtmp --> Rdest
	 * 
	 * 
	 * Strings:
	 * 
	 * a + b
	 * 
	 * 
	 * 
	 * Boolean short-circuit:
	 * ==============================
	 * 
	 * a && b (lTrue, lFalse)
	 * -----------------------
	 * 		visit(a, null, lFalse)
	 * 		visit(b, lTrue, lFalse)
	 * 
	 * a || b
	 * ---------
	 * 		visit(a, lTrue, null)
	 * 		visit(b, lTrue, lFalse)
	 * 
	 * 
	 * 
	 * Comparison:
	 * ==============================
	 * a < b
	 * ---------
	 * 		Compare	Rres1 Rres2 => Compare = Rres2 - Rres1
	 * 							   if Compare > 0
	 * 									Jump TrueLabel
	 * 							   else
	 * 									Jump FalseLabel
	 *		JumpLE FalseLabel
	 * a <= b
	 * ---------
	 * 		Compare Rres1 Rres2
	 * 		JumpL  FalseLabel
	 * a > b
	 * ---------
	 * 		Compare Rres1 Rres2
	 * 		JumpGE  FalseLabel
	 * 
	 * a >= b
	 * ---------
	 * 		Compare Rres1 Rres2
	 * 		JumpG  FalseLabel
	 * 
	 * a == b
	 * ---------
	 * 		Compare Rres1 Rres2
	 * 		JumpFalse  FalseLabel
	 * 
	 * a != b
	 * ---------
	 * 		Compare Rres1 Rres2
	 * 		JumpTrue  FalseLabel
	 * 
	 * 
	 */
	public List<ASMEntry> visit(BinaryExpr that, LoweringContext context)
	throws Exception {

		List<ASMEntry> list = new LinkedList<ASMEntry>();
		Operator op = that.getOp();

		if (Operator.BinaryMathOps.contains(op)) {
			assert( ContextKind.CanBeLval.contains(context.getKind()) );

			// evaluate both opernads of the expression:
			// evaluate the right to temporary register
			// and the right to the accumulator

			if (op.equals(Operator.PLUS) 
					&& isString(that.getLeft()) && isString(that.getRight())) {

				// send the arguments as parameters to the 
				// concatination function
				AnyOperand str1 = new AnyOperand();
				AnyOperand str2 = new AnyOperand();

				list.addAll(that.getLeft().accept(this, str1));
				list.addAll(that.getRight().accept(this, str2));

				assert (str1.getOp() != null && str2.getOp() != null);
				
				translateCall(list, new Label("__stringCat"), context,
						str1.getOp(), str2.getOp());
				
				return list;
			}
			else if (Operator.PlusMinusOps.contains(op)){
				// save instruction code
				Ops inst = null;
				switch (op) {
				case PLUS:	inst = Ops.ADD;	break;
				case MINUS:	inst = Ops.SUB; break;
				default: assert (false);
				}				
				AnyOperand right = new AnyOperand();
				RegOperand Rdest = new VirtualReg(); 
				list.addAll(that.getRight().accept(this, right));
				list.addAll(that.getLeft().accept(this, Rdest));
				list.add(new Instruction(inst, right.getOp(), Rdest));
				save(list, Rdest, context);
				return list;
			}
			else if (Operator.MulDivOps.contains(op)){
				AnyOperand right = new AnyOperand();				
				list.addAll(that.getRight().accept(this, right));
				switch (op) {
				case MOD:
				case DIV:
					list.add( new CommentEntry("division by zero check"));
					Label DBE = new Label("labelDBE");
					if (right.isImm()) {
						if (((IntImmediate)right.getOp()).getVal()==0)
							list.add(new Instruction(Ops.JMP, DBE));
					}
					else {
						list.add(new Instruction(Ops.CMP, new IntImmediate(0), right.getOp()));
						list.add(new Instruction(Ops.JE, DBE));
					}
					RegOperand Rleft = new VirtualReg(); 
					list.addAll(that.getLeft().accept(this, Rleft));
					list.add(new Instruction(Ops.MOV, Rleft, Regs.eax));
					list.add(new Instruction(Ops.CDQ));
					list.add(new Instruction(Ops.IDIV,
						right.isImm() ? right.getReg(list) : right.getOp()));
					save(list, (op==Operator.DIV)?Regs.eax:Regs.edx, 
										context);
					return list;
				case MUL:
					// TODO optimize Reg context
					RegOperand Rdest = new VirtualReg();
					list.addAll(that.getLeft().accept(this, Rdest));
					list.add(new Instruction(Ops.IMUL, right.getOp(), Rdest));
					save(list, Rdest, context);
					return list;
				default:
					assert (false);
				}
			}
		}
		else if (Operator.BoolOps.contains(op)) 
		{
			DoubleLabel labels;
			switch (context.getKind()) {
			case REG:
			case AnyOperand:
			case Mem:
				labels = new DoubleLabel(null,new Label());
				break;
			case DBLLabel:
				labels = (DoubleLabel)context;
				break;
			default:
				labels = null;
				assert(false);
			}

			if (Operator.LtGtOps.contains(op) || Operator.EqNEqOps.contains(op)) {

				// evaluate operand expressions
				AnyOperand right = new AnyOperand();
				AnyOperand left = new AnyOperand();

				list.addAll(that.getRight().accept(this, right));
				list.addAll(that.getLeft().accept(this, left));

				// add comparison instruction
				list.add(new Instruction(Ops.CMP, 
							right.getRegImm(list), left.getOp()));

				// TODO make it more efficient in scalar context
				switch (op) {
				case GT:
					addBranchCode(list, labels, 
							JumpCondition.GREATER, JumpCondition.LESSTHANEQUAL);
					break;
				case GTE:
					addBranchCode(list, labels, 
							JumpCondition.GREATEREQUAL, JumpCondition.LESSTHAN);
					break;
				case LT:
					addBranchCode(list, labels, 
							JumpCondition.LESSTHAN, JumpCondition.GREATEREQUAL);
					break;
				case LTE:
					addBranchCode(list, labels, 
							JumpCondition.LESSTHANEQUAL, JumpCondition.GREATER);
					break;
				case NEQ:
					addBranchCode(list, labels, 
							JumpCondition.FALSE, JumpCondition.TRUE);
					break;
				case EQ:
					addBranchCode(list, labels, 
							JumpCondition.TRUE, JumpCondition.FALSE);
					break;
				default:
					assert(false);
				}
			}
			else if (Operator.AndOrOps.contains(op)) {
				switch (op) {
				case AND:
					if (labels.falseLabel == null) {
						Label lFalse = new Label();
						list.addAll(that.getLeft().accept(this, 
								new DoubleLabel(null, lFalse)));
						list.addAll(that.getRight().accept(this, 
								new DoubleLabel(labels.trueLabel, lFalse)));
						list.add(new LabelDecl(lFalse));
					}
					else {
						list.addAll(that.getLeft().accept(this, 
								new DoubleLabel(null, labels.falseLabel)));
						list.addAll(that.getRight().accept(this, labels));
					}
					break;
				case OR:
					if (labels.trueLabel == null) {
						Label lTrue = new Label();
						list.addAll(that.getLeft().accept(this, 
								new DoubleLabel(lTrue, null)));
						list.addAll(that.getRight().accept(this, 
								new DoubleLabel(lTrue, labels.falseLabel)));
						list.add(new LabelDecl(lTrue));
					}
					else {
						list.addAll(that.getLeft().accept(this, 
								new DoubleLabel(labels.trueLabel, null)));
						list.addAll(that.getRight().accept(this, labels));
					}
					break;
				}
			}

			// if we are saving to a register, add 1/0 values
			if (ContextKind.CanBeLval.contains(context.getKind())) {
				Label lEnd = new Label();
				Operand dest;
				switch (context.getKind()) {
				case REG: case Mem:
					dest = (Operand)context; break;
				case AnyOperand:
					dest = new VirtualReg();
					((AnyOperand)context).set((RegOperand)dest);
					break;
				default: throw new Exception();
				}

				list.add(new Instruction(Ops.MOV, new IntImmediate(1), dest));
				list.add(new Instruction(Ops.JMP, lEnd));
				list.add(new LabelDecl(labels.falseLabel));
				list.add(new Instruction(Ops.MOV, new IntImmediate(0), dest));	
				list.add(new LabelDecl(lEnd));
			}
			return list;
		}
		assert (false);
		throw new Exception();
	}

/** helper functions * */
	private boolean isString(Expression expr) {
		return expr.getType().equals(StringType.getIt());
	}

	/**
	 * save a register to the context
	 */
	private void save(List<ASMEntry> list, RegOperand reg, LoweringContext context) {
		switch (context.getKind()) {
		case REG:
			RegOperand Rdst = (RegOperand)context;
			if (! Rdst.equals(reg)) {
				list.add(new Instruction(Ops.MOV, reg, Rdst));
			}
			break;
		case AnyOperand:
			AnyOperand any = (AnyOperand)context;
			any.set(reg);
			break;
		case DBLLabel:
			addBranchCode(list, (DoubleLabel) context, reg);
			break;
		case Mem:
			list.add(new Instruction(Ops.MOV, reg, (MemOperand)context));
			break;
		default:
			assert(false);
		}
	}
	
	/**
	 * save a specific register to the context
	 */
	private void save(List<ASMEntry> list, Regs reg, LoweringContext context) {
		switch (context.getKind()) {
		case AnyOperand:
			AnyOperand any = (AnyOperand)context;
			RegOperand Rtmp = new VirtualReg();
			list.add(new Instruction(Ops.MOV, reg, Rtmp));
			any.set(Rtmp);
			break;
		default:
			save(list, new MachineReg(reg), context);
		}
	}
	
	/**
	 * save a memory operand
	 */
	private void save(List<ASMEntry> list, MemOperand mem, LoweringContext context) {
		switch (context.getKind()) {
		case REG:
			RegOperand Rdst = (RegOperand)context;
			list.add(new Instruction(Ops.MOV, mem, Rdst));
			break;
		case AnyOperand:
			AnyOperand any = (AnyOperand)context;
			any.set(mem);
			break;
		case DBLLabel:
			addBranchCode(list, (DoubleLabel) context, mem);
			break;
		case Mem:
			if (! mem.equals((MemOperand)context)) {
				RegOperand Rtmp = new VirtualReg();
				list.add(new Instruction(Ops.MOV, mem, Rtmp));
				list.add(new Instruction(Ops.MOV, Rtmp, (MemOperand)context));
			}
			break;
		default:
			assert(false);
		}	
	}
	
	/**
	 * save an immediate operand
	 */
	private void save(List<ASMEntry> list, ImmOperand imm, LoweringContext context) {
		switch (context.getKind()) {
		case REG:
			RegOperand Rdst = (RegOperand)context;
			list.add(new Instruction(Ops.MOV, imm, Rdst));
			break;
		case AnyOperand:
			AnyOperand any = (AnyOperand)context;
			any.set(imm);
			break;
		case DBLLabel:
			addBranchCode(list, (DoubleLabel) context, imm);
			break;
		case Mem:
			list.add(new Instruction(Ops.MOV, imm, (MemOperand)context));
			break;
		default:
			assert(false);
		}	
	}
	
	/**
	 * adds code that treats RboolValue as a boolean value operand
	 * that is translated in a double-label context
	 * @param list
	 * @param dblLabel
	 * @param RboolValue
	 */
	private void addBranchCode(List<ASMEntry> list, DoubleLabel dblLabel,
			Operand boolValue) {
		list.add(new Instruction(Ops.CMP, new IntImmediate(1), boolValue));
		addBranchCode(list, dblLabel, JumpCondition.TRUE, JumpCondition.FALSE);
	}

	/**
	 * Adds to the list instructions that, based on a previous
	 * Compare instruction, jump to the true/false/both labels,
	 * handling the cases when one of the labels is null (if both
	 * are null no code is added)
	 * @param list the asm code buffer
	 * @param dblLabel the destination labels
	 * @param jumpTrue the true-label condition
	 * @param jumpFalse the false-label condition
	 */
	private void addBranchCode(List<ASMEntry> list, DoubleLabel dblLabel,
			JumpCondition jumpTrue, JumpCondition jumpFalse) {
		if (dblLabel.falseLabel != null)
			list.add(new Instruction(dblLabel.falseLabel, jumpFalse));
		if (dblLabel.trueLabel != null)
			list.add(new Instruction(dblLabel.trueLabel, jumpTrue));
		// remark: this can be improve by sometimes replacing one
		// of the conditional jumps with an undconditional one
	}

	/**
	 * translateMemberVar(a.b)
	 * -----------------------
	 * 		visit(a,Rinst)
	 * 		if 	l-value: MoveField Rop, Rinst.offset-of(b)
	 * 				else: MoveField Rinst.offset-of(b), Rop
	 * 
	 */
	private void translateMemberVar(List<ASMEntry> list, RegOperand Rinst,
			ClassInfo classInfo, String id, boolean isLvalue,
			LoweringContext context) {

		if (isLvalue) {
			assert (context.getKind()==ContextKind.AnyOperand);
		} 

		save(list, new MemOperand(Rinst,classInfo.getFieldOffset(id)*4+4), 
				context);
	}

	/**
	 * a <- b
	 * ------
	 * 		visit(b, ?)
	 * 		visit(a, ?)
	 *
	 */
	public List<ASMEntry> translateAssignment(Variable dest, Expression source)
	throws Exception {
		assert ((dest.getType() != null) && (source.getType() != null));

		List<ASMEntry> list;

		// compute the destination
		AnyOperand dst = new AnyOperand();
		list = dest.accept(this, dst);

		// ask the source to save the value
		list.addAll(source.accept(this, 
				(LoweringContext)dst.getOp()));
		
		return list;
	}

	/**
	 * get class info by class name
	 * @param classID the class ID
	 * @return the class info
	 */
	private ClassInfo getClassInfo(String classID) {
		SymTabEntry e = root.getSymTab().resolve(classID);
		return ((ClassDecl) e.getDeclNode()).getClassInfo();
	}

	/**
	 * get class info record by an expression object
	 * @param expr
	 * @return
	 */
	private ClassInfo getClassInfoByExpr(Expression expr) {
		ClassType classType = (ClassType) expr.getType();
		return classType.getDecl().getClassInfo();
	}

	/**
	 * get class info record by a class type object
	 * @param classType
	 * @return
	 */
	private ClassInfo getClassInfoByType(Type classType) {
		return ((ClassType) classType).getDecl().getClassInfo();
	}

	/**
	 * emit a function call
	 * @throws Exception 
	 */
	private void translateCall(List<ASMEntry> list, Operand addr,
			LoweringContext context, Operand ... args) 
	{
		// push caller-save
		list.add(new Instruction(Ops.PUSH, Regs.ecx));
		list.add(new Instruction(Ops.PUSH, Regs.edx));

		// push arguments
		for (int i = args.length; i>0; i--) 
		{
			list.add(new Instruction(Ops.PUSH, args[i-1]));
		}
		
		// call
		list.add(new Instruction(Ops.CALL, addr, null, Regs.ecx, Regs.edx));
		
		// remove arguments from stack
		list.add(new Instruction(Ops.ADD, new IntImmediate(args.length*4), Regs.esp));
		
		// pop caller-save
		list.add(new Instruction(Ops.POP, Regs.edx));
		list.add(new Instruction(Ops.POP, Regs.ecx));

		if (context != null)
			save(list, Regs.eax, context);
	}
	
	/**
	 * emit a function call
	 * @throws Exception 
	 */
	private void translateCall(List<ASMEntry> list, Operand addr, Operand instance,
			LoweringContext context, List<Expression> args) 
	throws Exception {
		
		List<Operand> argOps = new ArrayList<Operand>();
		
		// this
		if (instance != null)
			argOps.add(instance);
		
		// code to calculate arguments
		for (Expression arg: args) {
			AnyOperand dest = new AnyOperand();
			list.addAll(arg.accept(this, dest));
			argOps.add(dest.getOp());
		}
		
		translateCall(list, addr, context, argOps.toArray(new Operand[0]));
	};
	
	/**
	 * make a list with one comment
	 * @param comment the comment string
	 * @return the list
	 */
	private LinkedList<ASMEntry> makeComment(String comment) {
		return new LinkedList<ASMEntry>(new CommentEntry(comment));
	}

	/**
	 * 
	 * @param list
	 * @param val
	 */
	private void nullPtrCheck(List<ASMEntry> list, Operand val) {
		list.add(new CommentEntry("null pointer check"));
		list.add(new Instruction(Ops.CMP, new IntImmediate(0), val));
		list.add(new Instruction(Ops.JE, new Label("labelNPE")));
	}
}
